/**
 * @author jeymingwu
 * @date 2019/10/9 15:48
 */
public class Backpack {

    /**
     * 完全背包
     * @param A
     * @param V
     * @param m
     * @return
     */
    public int backpackI(int[] A, int[] V, int m) {
        int dp[][] = new int[A.length + 1][m + 1];
        for (int i = 1; i <= A.length; ++i) {
            for (int j = 0; j <= m; ++j) {
                dp[i][j] = dp[i - 1][j];
                if (j >= A[i - 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - A[i - 1]] + V[i - 1]);
                }
            }
        }

//        for (int i = 0; i <= A.length; ++i) {
//            for (int j = 0; j <= m; ++j) {
//                System.out.print(dp[i][j] + " ");
//            }
//            System.out.println();
//        }
        return dp[A.length][m];
    }

    /**
     * 01背包-优化（倒序）
     * @param A
     * @param V
     * @param m
     * @return
     */
    public int backpackII(int[] A, int[] V, int m) {
        int[] dp = new int[m + 1];
        for (int i = 1; i <= A.length; ++i) {
            for (int j = m; j >= A[i - 1]; --j) {
                dp[j] = Math.max(dp[j], dp[j - A[i - 1]] + V[i -1]);
            }
        }

//        for (int i = 0; i <= m; ++i) {
//            System.out.print(dp[i] + " ");
//        }
//        System.out.println();
        return dp[m];
    }

    /**
     * 01背包-正序
    * @param A
     * @param V
     * @param m
     * @return
     */
    public int backpackIII(int[] A, int[] V, int m) {
        int[][] dp = new int[A.length + 1][m + 1];
        for (int i = 1; i <= A.length; ++i) {
            for (int j = 0; j <= m; ++j) {
                dp[i][j] = dp[i - 1][j];
                if (j >= A[i - 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + V[i - 1]);
                }
            }
        }

        for (int i = 0; i <= A.length; ++i) {
            for (int j = 0; j <= m; ++j) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }

        return dp[A.length][m];
    }

    public static void main(String[] args) {
        int[] A = {2, 3, 4, 5};
        int[] V = {30, 50, 100, 200};
        Backpack backpack = new Backpack();
        System.out.println(backpack.backpackI(A, V, 8));
        System.out.println(backpack.backpackII(A, V, 8));
        System.out.println(backpack.backpackIII(A, V, 8));
    }
}
